import java.util.HashMap;

public class Solution {
    public int longestArithSeqLength(int[] nums) {
        int len = nums.length;

        int[][] dp = new int[len][len];

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                dp[i][j] = 2;
            }
        }

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                int num = 2 * nums[i] - nums[j];
                boolean flag = false;
                int k = i - 1;
                for ( ; k >= 0; k--) {
                    if (num == nums[k]) {
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    dp[i][j] = Math.max(dp[k][i] + 1, dp[i][j]);
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }

    public int longestArithSeqLength2(int[] nums) {
        int len = nums.length;

        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                dp[i][j] = 2;
            }
        }

        //key为nums的元素，value为对应的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 0);

        for (int i = 1; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int num = 2 * nums[i] - nums[j];
                int index = map.getOrDefault(num, -1);
                if (index >= 0 && index < i) {
                    dp[i][j] = Math.max(dp[index][i] + 1, dp[i][j]);
                }
            }
            map.put(nums[i], i);
        }

        int ret = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }
}
